package com.leetcode;

/**
 * 307. 区域和检索 - 数组可修改
 * 线段树
 */
public class Solution307_1 {

    class NumArray {
        private int[] segmentTree;
        private int n;

        public NumArray(int[] nums) {
            n = nums.length;
            segmentTree = new int[4 * n];
            // 构建线段树，下标从0开始
            build(0, 0, n - 1, nums);
        }

        public void update(int index, int val) {
            this.checkIndex(index);
            change(index, val, 0, 0, n - 1);
        }

        public int sumRange(int left, int right) {
            this.checkIndex(left);
            this.checkIndex(right);
            if (left > right) {
                throw new IllegalArgumentException("left > right");
            }
            return range(left, right, 0, 0, n - 1);
        }

        private void checkIndex(int index) {
            if (index < 0 || index >= n) {
                throw new IllegalArgumentException("out of index");
            }
        }

        // 构建线段树，下标从0开始
        private void build(int node, int start, int end, int[] nums) {
            if (start == end) {
                segmentTree[node] = nums[start];
                return;
            }
            int mid = mid(start, end);
            build(lchild(node), start, mid, nums);
            build(rchild(node), mid + 1, end, nums);
            update(node);
        }

        // 修改区间中某个下标元素的值
        private void change(int index, int val, int node, int start, int end) {
            if (start == end) {
                segmentTree[node] = val;
                return;
            }
            int mid = mid(start, end);
            if (index <= mid) {
                change(index, val, lchild(node), start, mid);
            } else {
                change(index, val, rchild(node), mid + 1, end);
            }
            update(node);
        }

        // 求范围区间和
        private int range(int left, int right, int node, int start, int end) {
            if (left == start && right == end) {
                return segmentTree[node];
            }
            int mid = mid(start, end);
            if (right <= mid) {
                return range(left, right, lchild(node), start,  mid);
            }
            if (left > mid) {
                return range(left, right, rchild(node), mid + 1, end);
            }
            return range(left, mid, lchild(node), start, mid) + range(mid + 1, right, rchild(node), mid + 1, end);
        }

        // 更新线段树的节点的值
        private void update(int node) {
            segmentTree[node] = segmentTree[lchild(node)] + segmentTree[rchild(node)];
        }

        // 计算左孩子的下标
        private int lchild(int node) {
            return 2 * node + 1;
        }

        // 计算右孩子的下标
        private int rchild(int node) {
            return 2 * node + 2;
        }

        // 计算区间中间值
        private int mid(int start, int end) {
            return start + ((end - start) >> 1);
        }

    }
}
